package 题目集.hash.字符串哈希;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 给定一个字符串 s 和一些长度相同的单词 words。
 * 找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 * 测试链接 : https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
 */
public class 串联所有单词的子串 {
    /**
     * words每个单词的长度为wn，words的单词个数len
     * 暴力解：
     *      1.先将words中所有单词放入hash表中
     *      2.枚举每一个位置作为起点，从这个起点len个长度wn的子串是否能覆盖words中的所有单词。
     *      时间复杂度：O(n*m)
     *  优化1：滑动窗口+哈希
     *      1.将words中所有单词放入hash表（字符串哈希）中。
     *      2.枚举每一个位置作为起点，判断该起点开始的子串是否能够由words中的所有单词组成。
     *          如果不能，则跳过已经匹配的长度，从匹配失败下一个位置开始重新匹配。
     *      时间复杂度：O(n)
     */
    static int wn; //单个单词的长度
    static long[] hash; //存储字符串的哈希值
    static long[] base; //存储P的幂次
    static Set<Long> set; //存储words中所有单词的哈希值
    static int lS; //字符串s的长度
    static int lW; //words的长度
    static int P = 131; //进制

    public List<Integer> findSubstring(String s, String[] words) {
        wn = words[0].length();
        List<Integer> res = new ArrayList<>();
        lS = s.length();
        lW = words.length;
        addWords(words);     //将words中的单词计算哈希值并放入set中
        buildHash(s.toCharArray()); //计算字符串s的哈希值
        int i = 1, j = wn;
        for (; j <= lS; i = j + 1) { //窗口 i-j是否符合要求
            int cnt = 1;
            Set<Long> resSet = new HashSet<>();     //用于去重
            long hash = 0;
            while (i <= j
                    && set.contains(hash = hash(i, i - 1 + cnt * wn))   //如果匹配单个成功
                    && !resSet.contains(hash))  //且没有重复
            {
                i += wn;
                resSet.add(hash);
                cnt++;
            }
            if (j - i + 1 == wn * lW) {    //如果匹配成功.有bug
                res.add(j - wn * lW);
            }
        }
        return res;
    }

    private void buildHash(char[] charArray) {
        base = new long[lS + 1];
        hash = new long[lS + 1];
        base[0] = 1;
        for (int i = 1; i <= lS; i++) {
            base[i] = base[i - 1] * P;
        }
        for (int i = 1; i <= lS; i++) {
            hash[i] = hash[i - 1] * P + charArray[i - 1];
        }
    }

    private void addWords(String[] words) {
        set = new HashSet<>();
        for (String w : words) {
            set.add(hash(w));
        }
    }

    private long hash(String w) {
        long res = 0;
        int len = w.length();
        for (int i = 0; i < len; i++) {
            res = res * P + w.charAt(i);
        }
        return res;
    }

    private long hash(int l, int r) {
        return hash[r] - hash[l - 1] * base[r - l + 1];
    }

    @Test
    public void test() {
//        String s = "barfoothefoobarman";
        String s = "ababab";
        String[] words = {"foo", "bar"};
        List<Integer> res = findSubstring(s, words);
        System.out.println(res);
    }

}
